#include "bitDiffNums.h"
#include <iostream>
int onesOfNum(int a) {
    int count = 0;
    while (a) {
        a = a & a - 1;
        count++;
    }
    return count;
}

int bitDiffNums(int a, int b) { return onesOfNum(a ^ b); }

int discardOdd(int n) {
    int count = 0;
    int index = 0;
    for (int i = 0; i < n; i++) {
        if (onesOfNum(i) > count) {
            count = onesOfNum(i);
            index = i;
        }
    }
    return index;
}

vector<int> arrayPrint(vector<vector<int>> arr, int n) {
    queue<pair<int, int>> nodes;
    vector<int> result;
    pair<int, int> loc = {0, n - 1};
    nodes.push(loc);
    vector<vector<bool>> visited =
        vector<vector<bool>>(n, vector<bool>(n, false));
    visited[0][n - 1] = true;
    while (!nodes.empty()) {
        loc = nodes.front();
        nodes.pop();
        int cx = loc.first;
        int cy = loc.second;
        result.push_back(arr[cx][cy]);

        if (cx >= 0 && cx <= n - 1) {
            if (cy - 1 < 0)
                cy = 1;
            loc = {cx, cy - 1};
            if (!visited[loc.first][loc.second]) {
                visited[loc.first][loc.second] = true;
                nodes.push(loc);
            }
        }
        if (cy >= 0 && cy <= n - 1) {
            if (cx + 1 > n - 1) {
                cx = n - 2;
            }
            loc = {cx + 1, cy};
            if (!visited[loc.first][loc.second]) {
                visited[loc.first][loc.second] = true;
                nodes.push(loc);
            }
        }
    }
    return result;
}
int maxProfitMt(vector<int> prices, int n) {
    if (n <= 0)
        return 0;

    int max_profit[4] = {-prices[0], 0, -prices[0], 0};
    for (int i = 1; i < n; i++) {
        max_profit[0] = std::max(max_profit[0], -prices[i]);
        max_profit[1] = std::max(max_profit[0] + prices[i], max_profit[1]);
        max_profit[2] = std::max(max_profit[1] - prices[i], max_profit[2]);
        max_profit[3] = std::max(max_profit[2] + prices[i], max_profit[3]);
    }
    return max_profit[3];
}
